package com.ma.trieTreePlus;


//前缀树
//解决了只能插入a-z的情况，现在所有字符都可以
public class trie {
    private Node root;
    trie(){
        root=new Node();
    }


    /**
     * 前缀树插入
     * @param word
     */
    public void insert(String word){
        if(word==null){
            return;
        }
        char[] str=word.toCharArray();
        Node node=root;
        node.pass++;
        int path=0;
        for(int i=0;i<str.length;i++){
            path=(int)str[i];//求ascll码,把ascll作为索引
            if(!node.nexts.containsKey(path)){
                node.nexts.put(path,new Node());

            }
            node=node.nexts.get(path);
            node.pass++;

        }
        node.end++;

    }


    /**
     * 前缀树查找
     * @param word
     * @return
     */
    public int search(String word){
        if(word==null){

            return 0;

        }
        char[] str=word.toCharArray();
        Node node=root;
        int index=0;
        for(int i=0;i<str.length;i++){
            index=(int)str[i];
            if(!node.nexts.containsKey(index)){
                return 0;
            }
            node=node.nexts.get(index);
        }
        return node.end;
    }


    /**
     * 查找有几个是word这个字符串作为的前缀
     * @param word
     * @return
     */
    public int prefixNumber(String word){
        if(word==null){

            return 0;

        }
        char[] str=word.toCharArray();
        Node node=root;
        int index=0;
        for(int i=0;i<str.length;i++){
            index=(int)str[i];
            if(!node.nexts.containsKey(index)){
                return 0;
            }
            node=node.nexts.get(index);
        }
        return node.pass;
    }


    /**
     * 删除
     * 如果删除到某一个字母pass为零了，说明不再经过这个字母了后面的路也就可以直接销毁了
     * @param word
     */
    public void delete(String word){
        if(search(word)!=0){
            char[] str=word.toCharArray();
            Node node=root;
            node.pass--;
            int path=0;
            for(int i=0;i<str.length;i++){
                path=(int) str[i];
                if(--node.nexts.get(path).pass==0){
                    node.nexts.remove(path);
                    return;
                }
                node=node.nexts.get(path);
            }
            node.end--;
        }
    }


}
